

/**
 * 
 * 题目：给定一个二叉树，判断它是否是高度平衡的二叉树。一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。
解题思路：
首先定义一个计算二叉树高度的方法。
然后对于每个节点，递归地计算其左右子树的高度。
如果左右子树的高度差的绝对值不超过 1，并且左右子树也都是高度平衡的，则该节点所代表的子树是高度平衡的。
 * 
 */
public class 否是高度平衡的二叉树 {
    
    public static void main(String[] args) {

        TN root = new TN(1);
        root.left = new TN(2);
        root.left.left = new TN(4);
        root.left.left.left = new TN(5);
        root.right = new TN(3);

        System.out.println("是否为平衡二叉树"+ nodeIsBanlance(root));
        

    }

    //计算节点高度
    private static int nodeHeight(TN node){

        if(null == node) return 0;

        return Math.max(nodeHeight(node.left), nodeHeight(node.right)) + 1;

    }

    //判断是否为平衡
    private static boolean nodeIsBanlance(TN node){

        if(null == node) return true;

        int leftHeigth = nodeHeight(node.left);
        int rightHeigth = nodeHeight(node.right);


        return Math.abs(leftHeigth - rightHeigth) <=1 
        && nodeIsBanlance(node.left)
         && nodeIsBanlance(node.right);

    }

    private static class TN {

        public int value;
        public TN left;
        public TN right;

        public TN(int value){

            this.value = value;
        }
    }
}
